package pl.edu.agh.jemo.evolution.selections.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import pl.edu.agh.jemo.evolution.population.Population;

/**
 * This class performs selection for SPEA2 Algorithm.
 * It is not an implementation of Tournament class, as it doesn't provide performTournament method.
 * The equivalent of that method works on two populations and modifies them both together.
 * However main task of that class is to select better specimen from population, so it logically is a part of tournament package.
 * 
 * @author Marcin Tkacz, Marcin Zbijowski
 *
 */
public class SPEA2EnvironmentalSelection {
	/**
	 * Expected archive population size, after tournament.
	 */
	protected int archiveSize = 0; 

	/**
	 * Fills new archive with best specimen from previous population and archive.
	 * All specimen with fitness less than 1 are trated as new archive population candidates.
	 * If new archive contains less selected than expected specimen, then it is filled with required number of specimen with bbest fitness.
	 * If there are too many specimen in new archive, some of them are discarded. The criteria for specimen rejection is density of population in place where specimen is.
	 *   
	 * @param population Population reference, ussed to determine new archive.
	 * @param archive Old archive used to determine new one.
	 * @return New population containing selected specimen.
	 */
	public Population generateNewArchive(
			final Population population,
			final Population archive) {

		Population newArchive = archive.clone();
		newArchive.clear();
		Population union = new Population();
		union.addAll(archive);
		union.addAll(population);
		
		// 1. Copy all nondominated specimen to new archive.
		for (int i = union.size()-1;  i >= 0 ; i--) {
			if (union.get(i).getFitness() < 1.) {
				newArchive.add(union.get(i));
				union.remove(i);
			}
		}

		// if the size is ok, return new archive
		if (newArchive.size() == archiveSize) {
			return newArchive;
		}

		// 2. Truncate
		if (newArchive.size() < archiveSize) {
			// if new archive is smaller
			// sort population and archive by fitness
			Collections.sort(union, Population.getFitnessComparator());
			// choose a number of best specimen equal to the difference in
			// archive sizes
			final int difference = archiveSize - newArchive.size();
			for (int i = 0; i < difference; i++) {
				newArchive.add(union.get(i));
			}
		} else {
			// if the new archive is bigger
			// calculate distances
			final List<List<Double>> distances = new ArrayList<List<Double>>();
			for (int i = 0; i < newArchive.size(); i++) {
				final List<Double> dist = new ArrayList<Double>();
				for (int k = 0; k < newArchive.size(); k++) {
					dist.add(newArchive.get(i).getEuclideanGenotypeSpaceDistance(
							newArchive.get(k)));
				}
				Collections.sort(dist);
				dist.remove(0); //remove itself
				distances.add(i, dist);
			}

			// while size is bigger
			while (newArchive.size() > archiveSize) {
				final int indexToRemove = findMinimumIndex(new ArrayList<Integer>(), distances, 0);
				distances.remove(indexToRemove);
				newArchive.remove(indexToRemove);
			}
		}

		return newArchive;
	}
	
	private void sortPopulation(Population population) {
		int dimensions = population.getDimensions();
		Population[] sortedPopulations = new Population[dimensions];

		for (int i = 0; i < dimensions; i++) {
			sortedPopulations[i] = new Population();
			sortedPopulations[i].setObjectiveFunctionSet(population.getObjectiveFunctionSet());
			sortedPopulations[i].addAll(population);
			Collections.sort(sortedPopulations[i], Population.getSpecimenDimensionGenotypeComparator(i));
		}
	}

	/**
	 * Finds specimen which is closest to all other specimen in new archive.
	 * It works on first dimension, and selects specimen with lowest distances to all other.
	 * If more than one specimen has the same lowest distance, this method is called for second dimension.
	 * Whole procedure is repeated until one specimen is selected.
	 * This method is used recursialy.
	 * 
	 * @param minDistancesIndexes List of all indexes with the lowest distance on previous dimension.
	 * @param distances Matrix of all distances between all specimen represented by List of Lists.
	 * @param depth Number of currently checked dimension.
	 * @return Index of specimen, that is the closest to all of his neighbours.
	 */
	private static int findMinimumIndex(List<Integer> minDistancesIndexes,
			List<List<Double>> distances, int depth) {
		if (depth >= distances.get(0).size()) {
			return minDistancesIndexes.get(0);
		}
		if (minDistancesIndexes.size() == 1) {
			return minDistancesIndexes.get(0);
		} else {
			if (minDistancesIndexes.size() == 0) {
				double minDistance = Double.MAX_VALUE;
				for (int i = 0; i < distances.size(); i++) {
					if (minDistance > distances.get(i).get(depth)) {
						minDistancesIndexes.clear();
						minDistance = distances.get(i).get(depth);
						minDistancesIndexes.add(i);
					} else if (minDistance == distances.get(i).get(depth)) {
						minDistancesIndexes.add(i);
					}
				}
			} else {
				List<Integer> temp = new ArrayList<Integer>();
				temp.addAll(minDistancesIndexes);
				for (Integer i : temp) {
					double minDistance = Double.MAX_VALUE;
					if (minDistance > distances.get(i).get(depth)) {
						minDistancesIndexes.clear();
						minDistance = distances.get(i).get(depth);
						minDistancesIndexes.add(i);
					} else if (minDistance == distances.get(i).get(depth)) {
						minDistancesIndexes.add(i);
					}
				}
			}
			return findMinimumIndex(minDistancesIndexes, distances, depth + 1);
		}
	}

	/**
	 * Sets required result archive size.
	 * 
	 * @param archiveSize New number of specimen that are supposed to be in new archive.  
	 */
	public void setArchiveSize(int archiveSize) {
		this.archiveSize = archiveSize;
	}
	
	/**
	 * Returns current archive size.
	 * 
	 * @return Number of specimen that are supposed to be in new archive.
	 */
	public int getArchiveSize() {
		return archiveSize;
	}
}
